#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};
class Solution {
public:
    vector<int> ret;
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> Q;
        int levelsize = 0;
        if (root != nullptr)
        {
            Q.push(root);
            levelsize = 1;
        }
        vector<int> ret;
        while (!Q.empty())
        {
            while (levelsize--)
            {
                TreeNode* front = Q.front();
                Q.pop();
                if (levelsize == 0)
                {
                    ret.push_back(front->val);
                }
                if (front->left)
                    Q.push(front->left);
                if (front->right)
                    Q.push(front->right);
            }
            levelsize = Q.size();
        }
        return ret;
    }

    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans(n - k + 1, -1);
        int cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            cnt = i == 0 || nums[i] - nums[i - 1] != 1 ? 1 : cnt + 1;
            if (cnt >= k)
                ans[i - k + 1] = nums[i];
        }
        return ans;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i)
        {
            if (target > matrix[i][n - 1]) continue;
            for (int j = 0; j < n; ++j)
            {
                if (target == matrix[i][j])
                    return true;
            }
        }
        return false;
    }

    int smallestDivisor(vector<int>& nums, int threshold) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        int ans = -1;
        while (left <= right)
        {
            int mid = (left + right) >> 1;
            int total = 0;
            for (int num : nums) {
                total += (num - 1) / mid + 1;
            }
            if (total <= threshold)
            {
                ans = mid;
                right = mid - 1;
            }
            else left = mid + 1;
        }
        return ans;
    }
};
